package org.wangliang181230.leetcode.problems.p_2;

/**
 * 2. 两数相加
 *
 * @author wangliang181230
 */
public class AddTwoNumbers_2 {

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode res = this.merge(l1, l2);
		this.carry(res);
		return res;
	}

	/**
	 * 合并两个链表，不考虑进位（递归）
	 *
	 * @param l1 链表1
	 * @param l2 链表2
	 * @return res 合并后的链表
	 */
	private ListNode merge(ListNode l1, ListNode l2) {
		if (l1 == null && l2 == null) {
			return null;
		} else if (l1 == null) {
			return new ListNode(l2.val, l2.next);
		} else if (l2 == null) {
			return new ListNode(l1.val, l1.next);
		}

		ListNode res = new ListNode();

		res.val = l1.val + l2.val;
		res.next = this.merge(l1.next, l2.next);

		return res;
	}

	/**
	 * 进位（递归）
	 *
	 * @param res 合并后的链表
	 */
	private void carry(ListNode res) {
		if (res.val >= 10) {
			if (res.next == null) {
				res.next = new ListNode(1);
			} else {
				res.next = new ListNode(res.next.val + 1, res.next.next);
			}
			res.val -= 10;
		}
		if (res.next != null) {
			this.carry(res.next);
		}
	}
}
